Regular expression matching

Time: O(MxN); Space: O(N); hard

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ’*’.

  • ‘.’ Matches any single character.

  • ’*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

  • s could be empty and contains only lowercase letters a-z.

  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input: s = “aa”, p = “a”

Output: False

Explanation:

  • “a” does not match the entire string “aa”.

Example 2:

Input: s = “aa”, p = “a*”

Output: True

Explanation:

  • ’*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:

Input: s = “ab”, p = “.*”

Output: True

Explanation:

  • “.” means “zero or more () of any character (.)”.

Example 4:

Input: s = “aab”, p = “c*a*b”

Output: True

Explanation:

  • c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.

Example 5:

Input: s = “mississippi”, p = “mis*is*p*.”

Output: False

1.

[20]:

class Solution1(object):
    """
    Time: O(M*N)
    Space: O(N)
    """
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: a boolean
        """
        k = 3
        result = [[False for j in range(len(p) + 1)] for i in range(k)]

        result[0][0] = True
        for i in range(2, len(p) + 1):
            if p[i-1] == '*':
                result[0][i] = result[0][i-2]

        for i in range(1,len(s) + 1):
            if i > 1:
                result[0][0] = False
            for j in range(1, len(p) + 1):
                if p[j-1] != '*':
                    result[i % k][j] = result[(i-1) % k][j-1] and \
                    (s[i-1] == p[j-1] or p[j-1] == '.')
                else:
                    result[i % k][j] = result[i % k][j-2] or \
                    (result[(i-1) % k][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))

        return result[len(s) % k][len(p)]

[21]:

sol = Solution1()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False

s = "aa"
p = "a*"
assert sol.isMatch(s, p) == True

s = "ab"
p = ".*"
assert sol.isMatch(s, p) == True

s = "aab"
p = "c*a*b"
assert sol.isMatch(s, p) == True

s = "mississippi"
p = "mis*is*p*."
assert sol.isMatch(s, p) == False

2. Dynamic programming

[22]:

class Solution2(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: a boolean
        """
        result = [[False for j in range(len(p) + 1)] for i in range(len(s) + 1)]

        result[0][0] = True
        for i in range(2, len(p) + 1):
            if p[i-1] == '*':
                result[0][i] = result[0][i-2]

        for i in range(1,len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j-1] != '*':
                    result[i][j] = result[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
                else:
                    result[i][j] = result[i][j-2] or (result[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))

        return result[len(s)][len(p)]

[23]:

sol = Solution2()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False

s = "aa"
p = "a*"
assert sol.isMatch(s, p) == True

s = "ab"
p = ".*"
assert sol.isMatch(s, p) == True

s = "aab"
p = "c*a*b"
assert sol.isMatch(s, p) == True

s = "mississippi"
p = "mis*is*p*."
assert sol.isMatch(s, p) == False

3. Iteration

[24]:

class Solution3(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: a boolean
        """
        p_ptr, s_ptr, last_s_ptr, last_p_ptr = 0, 0, -1, -1
        last_ptr = []

        while s_ptr < len(s):
            if p_ptr < len(p) and (p_ptr == len(p) - 1 or p[p_ptr + 1] != '*') and \
              (s_ptr < len(s) and (p[p_ptr] == s[s_ptr] or p[p_ptr] == '.')):
                    s_ptr += 1
                    p_ptr += 1
            elif p_ptr < len(p) - 1 and (p_ptr != len(p) - 1 and p[p_ptr + 1] == '*'):
                p_ptr += 2
                last_ptr.append([s_ptr, p_ptr])
            elif  last_ptr:
                [last_s_ptr, last_p_ptr] = last_ptr.pop()
                while last_ptr and p[last_p_ptr - 2] != s[last_s_ptr] and p[last_p_ptr - 2] != '.':
                    [last_s_ptr, last_p_ptr] = last_ptr.pop()

                if p[last_p_ptr - 2] == s[last_s_ptr] or p[last_p_ptr - 2] == '.':
                    last_s_ptr += 1
                    s_ptr = last_s_ptr
                    p_ptr = last_p_ptr
                    last_ptr.append([s_ptr, p_ptr])
                else:
                    return False
            else:
                return False

        while p_ptr < len(p) - 1 and p[p_ptr] == '.' and p[p_ptr + 1] == '*':
            p_ptr += 2

        return p_ptr == len(p)

[25]:

sol = Solution3()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False

s = "aa"
p = "a*"
assert sol.isMatch(s, p) == True

s = "ab"
p = ".*"
assert sol.isMatch(s, p) == True

s = "aab"
p = "c*a*b"
assert sol.isMatch(s, p) == True

s = "mississippi"
p = "mis*is*p*."
assert sol.isMatch(s, p) == False

4. Recursive

[26]:

class Solution4(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: a boolean
        """
        if not p:
            return not s

        if len(p) == 1 or p[1] != '*':
            if len(s) > 0 and (p[0] == s[0] or p[0] == '.'):
                return self.isMatch(s[1:], p[1:])
            else:
                return False
        else:
            while len(s) > 0 and (p[0] == s[0] or p[0] == '.'):
                if self.isMatch(s, p[2:]):
                    return True
                s = s[1:]

            return self.isMatch(s, p[2:])

[27]:

sol = Solution4()

s = "aa"
p = "a"
assert sol.isMatch(s, p) == False

s = "aa"
p = "a*"
assert sol.isMatch(s, p) == True

s = "ab"
p = ".*"
assert sol.isMatch(s, p) == True

s = "aab"
p = "c*a*b"
assert sol.isMatch(s, p) == True

s = "mississippi"
p = "mis*is*p*."
assert sol.isMatch(s, p) == False